//给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 
//
// 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [4,6,7,7]
//输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [4,4,3,2,1]
//输出：[[4,4]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 15 
// -100 <= nums[i] <= 100 
// 
// Related Topics 位运算 数组 哈希表 回溯 👍 426 👎 0

package leetcode.editor.cn;

import java.util.*;

class IncreasingSubsequences {
    public static void main(String[] args) {
        Solution solution = new IncreasingSubsequences().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
    /*public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length == 0) {
            return res;
        }
        backtracking(nums, 0);
        return res;
    }

    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    */

        /**
         * 使用hash法来进行判重
         */
    /*
    public void backtracking(int[] nums, int startIndex) {
        if (path.size() > 1) {
            res.add(new ArrayList<>(path)); // 取树枝上的值
        }

        Map<Integer, Integer> map = new HashMap<>();    // 用来判断本层是否重复使用，每次for之前，也就是每层都需要重新使用一个map来判断

        for (int i = startIndex; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.getLast()) {  // 如果2个数不是递增，跳过此次选择
                continue;
            }

            if (map.getOrDefault(nums[i], 0) > 0) { // 本层中已经取过此元素
                continue;
            }

            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1); // 去过就放入map中
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();  // 回溯
        }
    }*/
        public List<List<Integer>> findSubsequences(int[] nums) {
            backtracking(nums, 0);
            return res;
        }

        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();

    /*public void backtracking(int[] nums, int startIndex) {
        // 大小至少为2才可以算作一个递增子序列
        if (path.size() > 1) {
            res.add(new ArrayList<>(path));
        }

        if (startIndex >= nums.length) {
            return;
        }

        // 使用数组来表示哈希表
        // 由于题目给的数是在[-100,100]之间，所以申请201个单元
        int[] used = new int[201];
        for (int i = startIndex; i < nums.length; i++) {
            // 不是递增序列或者同一层出现过，直接跳过此次选取
            // 注意是path的最后一个元素进行比较
            if ((!path.isEmpty() && nums[i] < path.getLast()) || used[nums[i] + 100] == 1) continue;
            path.add(nums[i]);
            used[nums[i] + 100] = 1;
            backtracking(nums, i + 1);
            // 错误操作：此时的哈希表表只代表本层是否使用过，和下一层无关
            // 所以下一次回溯时，和本层是否选取无关系，所以不能回溯
            // 注意和前面排序之后使用used区分
            // used时整个所有数都是用used来判断，所以有关系
            // used[nums[i] + 100] = 0;
            path.removeLast();
        }
    }*/

        // 使用set，求递增序列，不能排序
        public void backtracking(int[] nums, int startIndex) {
            if (path.size() > 1) {
                res.add(new LinkedList<>(path));
            }

            if (startIndex == nums.length) {
                return;
            }

            // 不能排序的去重操作使用set
            Set<Integer> set = new HashSet<>();
            for (int i = startIndex; i < nums.length; i++) {
                // 注意不等使用nums[i]和nums[i-1]大小比较，需要使用path.getLast()，应为没有经过排序，可能上一次选择的不是i-1
                if ((!path.isEmpty() && nums[i] < path.getLast()) || set.contains(nums[i])) continue;
                path.add(nums[i]);
                set.add(nums[i]);
                backtracking(nums, i + 1);
                // 每一层一个set，所以不用回溯，下一层就是另一个set
                path.removeLast();
            }

        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
